//自己
class Solution {
public:
    int triangleNumber(vector<int>& nums)
    {
        //1. 排升序
        sort(nums.begin(), nums.end());//默认仿函数是less升序, 先排出小的
        //2. 
        int c=nums.size()-1, left=0, right=c-1, count=0;//c是最大值下标
        while (c > 1)//c左边至少要有两个元素
        {
            while (left < right)
            {
                //cout << left << " " << right;
                if (nums[left] + nums[right] > nums[c])
                {
                    count += right - left;
                    --right;
                }
                else 
                {
                    ++left;
                }
                //cout << endl;
            }
            --c;
            //注意: 每次更换c后, left, right都要重置
            left = 0;
            right = c - 1;
        }
        return count;
    }
};
//时间复杂度O(n^2 + n*logn)
//空间O(1)


//答案
class Solution {
public:
    int triangleNumber(vector<int>& nums)
    {
        //1. 排升序
        sort(nums.begin(), nums.end());//默认仿函数是less升序, 先排出小的
        //2. 利用双指针 + 单调性 快速统计出三元组个数
        int ret = 0, n = nums.size();
        for (int i=n-1; i>=2; --i)//固定最/次大值的左边至少要有两个元素
        {
            //注意: 每次更换c后, left, right都要重置
            int left = 0, right = i - 1;
            while (left < right)
            {
                if (nums[left] + nums[right] > nums[i]) //ret += right - left, --right;//逗号表达式
                {
                    ret += right - left;
                    --right;
                }
                else 
                {
                    ++left;
                }
            }
        }
        return ret;
    }
};
//时间复杂度O(n^2 + n*logn)
//空间O(1)